package com.desin.modle.datastruct.hashtable18;

public class MyHashTable<K,V> {
    private static final int DEFAULT_SIZE = 8;

    /**
     * 装载因子
     */
    private static final float LOAD_FACTOR = 0.75f;

    private Entry<K,V>[] table;

    public MyHashTable() {
        table = new Entry[DEFAULT_SIZE];
    }

    //hash中元素的个数
    private int size;

    //hash中使用索引的个数，也就是桶的葛素
    private int use;

    /**
     * 散列函数
     * <p>
     * 参考hashmap散列函数
     *
     * @param key
     * @return
     */
    private int hash(Object key) {
        int h;
        return (key == null) ? 0 : ((h = key.hashCode()) ^ (h >>> 16)) % table.length;
    }

    public void put(K key,V value){
        int index = hash(key);
        Entry<K, V> entry = table[index];

        if(entry==null){
            table[index] = new Entry<>(null,null,null);
        }

        Entry<K, V> tmp = table[index];
        if(tmp.next==null){
            tmp.next = new Entry(key,value,null);
            size++;
            use++;
            if(use>=table.length*LOAD_FACTOR){
                resize();
            }
            else{
                do{
                    tmp = tmp.next;
                    if(tmp.key == key){
                        tmp.value = value;
                        return;
                    }
                }while (tmp.next!=null);

                Entry next = table[index].next;
                table[index].next = new Entry(key,value,next);
                size++;
            }
        }

    }

    private void resize() {
        Entry<K,V>[] oldTable = table;
        table = new Entry[table.length*2];
        use = 0;
        for(int i=0;i<oldTable.length;i++){
            Entry<K, V> tmp = oldTable[i];
            if(tmp==null||tmp.next==null){
                continue;
            }
            while (tmp!=null){
                tmp = tmp.next;
                int index = hash(tmp.key);
                if(table[index]==null){
                    use++;
                    table[index] = new Entry<>(null,null,null);
                }
                table[index].next = new Entry(tmp.key,tmp.value,table[index].next);
            }
        }
    }

    private void remove(K key){
        int index = hash(key);
        Entry<K, V> e = table[index];
        if(e==null||e.next==null){
            return;
        }
        Entry<K,V> pre;
        Entry<K, V> hashNode = table[index];
        do{
            pre = e;
            e = e.next;
            if(e.key == key){
                pre.next = e.next;
                size--;
                if(hashNode.next==null){
                    use--;
                }
                return;
            }

        }while (e.next!=null);
    }

    private V get(K key){
        int index = hash(key);
        Entry bucketEntry = table[index];
        if(bucketEntry==null||bucketEntry.next==null){
            return null;
        }
        Entry<K,V> entryNext = bucketEntry.next;
        while(entryNext!=null){
            if(entryNext.key == key){
                return entryNext.value;
            }
            entryNext = entryNext.next;
        }
        return null;
    }


    class Entry<K,V>{
        private K key;
        private V value;
        private Entry next;

        public Entry(K key, V value, Entry next) {
            this.key = key;
            this.value = value;
            this.next = next;
        }
    }
}
